1. Field of the Invention
The present invention broadly relates to a data processing method and apparatus, an image encoding method and apparatus, an image decoding method and apparatus, an image transmitting method, and recording mediums. More particularly, the invention relates to a data processing method and apparatus, an image encoding method and apparatus, an image decoding method and apparatus, an image transmitting method, and recording mediums, in all of which quantizing errors are minimized, and temporal jitter of motion pictures, which is caused by a change in the phase of ringing noise between frames, is suppressed.
2. Description of the Related Art
In quantization processing executed to order to perform digital-data compression, input data c is, in general, quantized according to the following equation: EQU c'=int(c/Q+0.5) (1)
where Q indicates the quantization step size, and into represents the function for rounding down the remainder. In contrast, to perform de-quantization processing for reproducing the data, the following equation is calculated. EQU c"=c'.times.Q (2)
The foregoing two processing operations expressed by the respective equations (1) and (2) are referred to as "linear quantization" and "linear de-quantization", respectively. The value nQ (n is an integer) of the reproduced data designates, as illustrated in FIG. 25, the center value of each of the ranges incremented by the respective quantizing steps, and corresponds to all the input data in a range represented by the following expression. EQU nQ-Q/2.ltoreq.c&lt;nQ+Q/2 (3)
On the other hand, nonlinear quantizing processing is executed on the data having a large frequency distribution, such as the one shown in FIG. 26. More specifically, as shown in FIG. 27, a larger level of distribution frequency is quantized by a smaller quantizing step in order to decrease the overall quantizing errors.
FIG. 28 is a schematic diagram illustrating an example of conventional motion-picture encoding apparatuses. In this encoding apparatus 1, motion-picture data to be encoded is input into a frame memory 12 via an input terminal and stored therein. A motion-vector detector 11 detects a motion vector v from the input image stored in the frame memory 12 generally by performing block matching by a block unit of non-overlapping and small 16.times.16-pixel regions (hereinafter referred to as "the macroblocks"). Alternatively, to obtain higher precision a matching operation by a half-pixel unit may be sometimes performed.
A motion compensator 20, which contains a frame memory 21, predicts the individual pixel values of the image to be encoded from the wholly encoded and partially decoded previous image which is stored in the frame memory 21. The predicted value I'[i,j,t] of the pixel I[i,j,t] located at the position (i,j) of the image which was input at time t is determined from the motion vector v=(vx(i,j,t), vy(i,j,t)) by the following equation: EQU I'[i,j,t]=(I[i',j',t-T]+I[i'+1,j',t-T]+I[i',j'+1,t-T]+I[i'+1,j'+1,t-T]/4 (4)
wherein i' and j' are expressed by the following equation: EQU i'=int(i+vx(i,j,t)T) EQU j'=int(j+vy(i,j,t)T)
wherein T indicates a difference between the time at which the image I to be predicted was input and the time at which the previous image stored in the frame memory 12 was input; (I[i',j',t-T], I[i'+1,j',t-T], I[i',j'+1,t-T], and I[i'+1,j'+1,t-T] on the right side of equation (4) represent the pixel values stored in the frame memory 21; and int(x) designates the maximum integer not greater than x.
A differential-image generator 13 calculates a difference between the pixel value to be encoded and the predicted value obtained by the motion compensator 20, and then calculates the sum s of the absolute values of the differences within each macroblock according to the following equation:
[Mathematical equation 1] ##EQU1##
wherein MB.sub.pq indicates a macroblock designated by pq. When the value of equation (5) is smaller than the threshold T1, each differential value corresponding to the designated macroblock is output. In contrast, when the value of equation (5) is equal to or greater than the threshold T1, the pixel value to be encoded rather than the differential value is output. The macroblocks from which the pixel values are output are referred to as "the intra-macroblocks", while the macroblocks other than the intra-macroblocks are referred to as "the inter-macroblocks".
The flag f representing whether or not the macroblock to be output is an intra-macroblock is transmitted to a variable-length encoder/multiplexer 16 and is multiplexed with a bit stream, and is further sent to an image adder 19.
A discrete cosine transform (DCT) unit 14 performs two-dimensional DCT on a 8.times.8-pixel block. Then, a quantizer(Q) 15 quantizes the DCT coefficient c obtained by the DCT unit 14 by using a suitable step size Q according to the following equation. EQU c'=int(c/Q) (6)
The quantized DCT coefficient c' is sent to the variable-length encoder/multiplexer 16 and de-quantizer (Q.sup.-1) 17. The de-quantizer 17 de-quantizes the DCT coefficient c' according to the following equation by using the same step size Q as the one used in the quantizer 15. EQU c"=c'.times.Q (7)
Inverse DCT (IDCT) is conducted on the de-quantized data which is expressed by a 8.times.8-pixel block by an inverse discrete cosine transform (IDCT) unit 18.
The image adder 19 reproduces the pixel value from the data output from the IDCT unit 18 and the predicted value output from the motion compensator 20 in accordance with the flag f transmitted from the differential-image generator 13. If the flag f represents an intra-macroblock, the data output from the IDCT unit 18 represents the pixel value. Accordingly, no processing is performed in the image adder 19. In contrast, if the flag f indicates an inter-macroblock, the image adder 19 adds the predicted value from the motion compensator 20 to the data from the IDCT unit 18, and then reproduces the pixel value. The reproduced pixel value is transmitted to the motion compensator 20 and stored in the frame memory 21.
The variable-length encoder/multiplexer 16 variable-length encodes and multiplexes the following elements: the DCT coefficient c quantized by the quantizer 15, the motion vector v detected by the motion-vector detector 11, and the flag f obtained by the differential-image generator 13. The multiplexed data in the form of a bit stream is then transmitted to a predetermined transmission line 22 or recorded on a recording medium 23.
FIG. 29 is a block diagram illustrating an example of a motion-picture decoding apparatus which receives the bit stream output from the motion-picture encoding apparatus 1 shown in FIG. 28 and decodes the received bit stream. The decoding apparatus 31 receives the bit stream from the predetermined transmission line 22 or the recording medium 23 via an input terminal. Then, a de-multiplexer/variable-length decoder 41 variable-length decodes and demultiplexes the bit stream encoded and multiplexed by the variable-length encoder/multiplexer 16 of the encoding apparatus 1, thereby reproducing the quantized DCT coefficient, the motion vector v, and the flag f from the bit stream. The reproduced DCT coefficient is transmitted to the de-quantizer 42; the motion vector v is sent to a motion compensator 45; and the flag f is fed to an image adder 44.
The de-quantizer (Q.sup.-1) 42 and an IDCT unit 43 of the decoder 31 are similar to the de-quantizer (Q.sup.-1) 17 and the IDCT unit 18 of the encoding apparatus 1, and de-quantization processing expressed by equation (7) is performed in the de-quantizer (Q.sup.-1) 42, and IDCT is then conducted in the IDCT unit 43.
The image adder 44, which is similar to the image adder 19 of the encoding apparatus 1, reproduces the bit stream to obtain the pixel value of the reproduced image in the following manner. If the flag f transmitted from the de-multiplexer/variable-length decoder 41 indicates an intra-macroblock, the image adder 44 reproduces the data output from the IDCT unit 43. On the other hand, if the flag f represents an inter-macroblock, the adder 44 adds the predicted value generated by the motion compensator 45 to the data from the IDCT unit 43. The resulting pixel value is stored in a frame memory 46 provided for the motion compensator 45 in order to create a predicted image.
The motion compensator 45, which is similar to the counterpart of the encoding apparatus 1, predicts the individual pixel values of the image to be decoded with the use of the motion vector v obtained by the variable-length decoder 41 and the image stored in the frame memory 46 of the motion compensator 45.
FIGS. 30 and 31 respectively illustrate a motion-picture encoding apparatus 1 and a motion-picture decoding apparatus 31, both of which utilize the wavelet transform method. In the encoding apparatus 1 and the decoding apparatus 31 shown in FIGS. 30 and 31, the DCT unit 14, and the IDCT units 18 and 43 shown in FIGS. 28 and 29 are substituted for a wavelet transformer 51 and inverse wavelet transformers 52 and 61, respectively. The other components, such as the quantizer 15, the de-quantizers 17 and 42, and the motion compensators 20 and 45 are similar to those illustrated in FIGS. 28 and 29.
The differential-image generator 13, as well as the generator 13 shown in FIG. 28, determines whether the flag f represents an intra-macroblock or an inter-macroblock. If, however, it is determined that the macroblock is an intra-macroblock, the differential-image generator 13 illustrated in FIG. 30, unlike the generator 13 shown in FIG. 28, calculates the average ave of the pixel values within the macroblock according to the following equation:
[Mathematical equation 2] ##EQU2##
where N.sub.MBpq represents the number of pixels (16.times.16 pixels) within the macroblock.
A differential value obtained by subtracting the average ave from each of the pixel values within the macroblock is output to a wavelet transformer 51 from the differential-image generator 13. Meanwhile, the average ave of the intra-macroblock is transmitted to the variable-length encoder/multiplexer 16. The average ave is also sent to the image adder 19 and is used for reproducing the image.
The image adder 19 reproduces the pixel values of an intra-macroblock by adding the macroblock average ave output from the differential-image generator 13 to the data which has been inverse-wavelet transformed by the inverse wavelet transformer 52. Conversely, the image adder 19 reproduces the pixel values of an inter-macroblock in a manner similar to the image adder 19 used in the encoding operation performed by utilizing the DCT method. The differential-image generator 13 outputs a difference between the input pixel value and the predicted value of a predicted image output from the motion compensator 20, and the differential value is wavelet-transformed in the wavelet transformer 51. The image adder 19 then adds the predicted value generated by the motion compensator 20 to the data which has been inverse-wavelet transformed by the inverse-wavelet transformer 52, thereby reproducing the pixel values.
It should be noted that a decoding operation similar to the operation discussed above is executed by the inverse-wavelet transformer 61, the image adder 44, and the motion compensator 45 of the motion-picture decoding apparatus 31.
An example of the configuration of the wavelet transformer 51 is shown in FIG. 32. The image data I[i,j] input from the differential-image generator 13 is transmitted to an analyzing horizontal low-pass filter 71 and an analyzing horizontal high-pass filter 101 so as to perform frequency-band division on the input data in the horizontal direction of the image. As the above-described filters 71 and 101, linear filters having coefficients, such as those represented by FIGS. 33A and 33B, respectively, may be used.
The analyzing filters employed in the wavelet division, such as those shown in FIG. 32, and the synthesizing filters used in the wavelet synthesizing, such as those illustrated in FIG. 34, which will be explained later, are configured to completely or approximately satisfy the following equations, respectively: EQU H0(-z)F0(z)+H1(-z)F1(z)=0 (9) EQU H0(z)F0(z)+H1(z)F1(z)=2z-L (10)
where H0(z), H1(z), F0(z), and F1(z) respectively designate the transfer function of analyzing low-pass filters 71, 74, 77, 80, 87, and 104, the transfer function of analyzing high-pass filters 75, 82, 84, 89, 101 and 106, the transfer function of synthesizing low-pass filters 123, 129, 143, 152, 158 and 162, and the transfer function of synthesizing high-pass filters 127, 147, 149, 156, 166 and 168; and L indicates a certain integer. It is thus expected that the signal synthesized in accordance with the foregoing conditions wholly or approximately coincides with the input signal which has not undergone band-pass division processing. The coefficients provided for the synthesizing low-pass filters and the synthesizing high-pass filters shown in FIG. 34 are respectively shown in FIGS. 35A and 35B by way of example.
Referring back to FIG. 32, the analyzing low-pass filter 71 extracts a horizontal low-frequency-band signal, which indicates a low-frequency component in the horizontal direction, from the input image data I[i,j], and outputs the extracted signal to a horizontal sub-sampling unit 72. The sub-sampling unit 72 reduces the data every other sample according to the following equation: EQU X[i'j']=X[i,j],i'i/2 (11)
where X equals L.
A memory 73 is a storage device formed of a plurality of line memory units in which the data required for the analyzing vertical low-pass filter 74 or the vertical high-pass filter 75 is stored. The memory 73 has the same number of line memory units as the taps of the filter used in the filtering operation in the vertical direction. If the filters having coefficients shown in FIGS. 33A and 33B, for example, are used as the low-pass filter 74 and the high-pass filter 75, respectively, nine line memory units are provided in accordance with a larger number of taps of the low-pass filter having.
In order to conduct the frequency-band division in the vertical direction of the image, the vertical low-pass filter 74 and the vertical high-pass filter 75 respectively perform low-pass filtering and high-pass filtering on the data stored in the memory 73. The same types of filters used in the horizontal filtering operation, i.e., the horizontal low-pass filter 71 and the horizontal high-pass filter 101, may be used for the vertical filtering operation.
In the meantime, the analyzing horizontal high-pass filter 101 separates a horizontal high-frequency-band signal H[i,j] from the image data I[i,j]. Then, a horizontal sub-sampling unit 102 samples the separated signal according to the foregoing equation (11) (wherein X equals H) and stores the sampled data in a memory 103. The low-pass filter 104 and the high-pass filter 106, in a manner similar to the low-pass filter 74 and the high-pass filter 75, respectively, perform low-pass filtering and high-pass filtering on the data output from the memory 103 in the vertical direction of the image.
A signal LL[i',j] output from the vertical low-pass filter 74 and a signal LH[i',j] output from the high-pass filter 75, both signals being extracted from the horizontal low-frequency-band signal L[i',j] output from the horizontal sub-sampling unit 72, and a signal HL[i',j] output from the low-pass filter 104 and a signal HH[i',j] output from the high-pass filter 106, both signals being separated from the horizontal high-frequency-band signal H[i',j] output from the horizontal sub-sampling unit 102, are respectively transmitted to vertical sub-sampling units 76, 91, 105 and 107. The sub-sampling units 76, 91, 105 and 107 then execute sub-sampling processing on the respective signals, i.e., reduces the signals every other line, in the vertical direction of the image according to the following equation: EQU X[i',j']=X[j',j], j'=j/2 (12)
where X equals LL, LH, HL or HH.
The frequency-band signals LH[i',j'], HL[i',j'], and HH[i',j'], which have been respectively sub-sampled by the units 91, 105 and 107, are directly output to the quantizer 15 from the wavelet transformer 51.
Moreover, the signal LL[i',j'], which has been low-pass filtered both in the horizontal and vertical directions, output from the vertical sub-sampling unit 76, is input into the second-level horizontal low-pass filter 77 and the horizontal high-pass filter 84. Subsequently, the operations similar to the processing executed in the above-described horizontal low-pass filter 71, the horizontal sub-sampling unit 72, the memory 73, the vertical low-pass filter 74, the vertical high-pass filter 75, and the vertical sub-sampling units 76 and 91, are respectively performed in the horizontal low-pass filter 77, the horizontal sub-sampling unit 78, the memory 79, the vertical low-pass filter 80, the vertical high-pass filter 82, and the vertical sub-sampling units 81 and 83.
Further, the operations similar to the processing executed in the foregoing horizontal high-pass filter 101, the horizontal sub-sampling unit 102, the memory 103, the vertical low-pass filter 104, the vertical high-pass filter 106, and the vertical sub-sampling units 105 and 107 are respectively performed in the horizontal high-pass filter 84, the sub-sampling unit 85, the memory 86, the vertical low-pass filter 87, the vertical high-pass filter 89, and the vertical sub-sampling units 88 and 90. As a consequence, the band-divided signals LLLL[i",j"], LHLL[i",j"], HLLL[i",j"], and HHLL[i",j"] are generated. The output signals LLLL[i",j"], LHLL[i",j"], HLLL[i",j"], HHLL[i",j"], and LH[i',j'], HL[i',j'], HH[i',j'] are used as wavelet coefficients corresponding to the respective frequency bands.
Conversely, the inverse-wavelet transformer 52 (the inverse-wavelet transformer 61 is also constructed similar to the transformer 52) shown in FIG. 34 sequentially synthesizes the respective frequency-band signals output from the wavelet transformer 51 illustrated in FIG. 32, i.e, the wavelet coefficients LLLL[i",j"], LHLL[i",j"], HLLL[i",j"], and HHLL[i",j"], and LH[i',j'], HL[i',j'], HH[i',j'], thereby reproducing the image.
More specifically, the inverse-wavelet transformer 52 first synthesizes the signals LLLL[i",j"], LHLL[i",j"], HLLL[i",j"], and HHLL[i",j41 ], which have been band-divided by the two levels of filters of the wavelet transformer 51. The input signals are stored in memory devices 121, 125, 141 and 145, respectively, each formed of a plurality of line memory units. The memory devices 121, 125, 141 and 145 are provided with line memory units having the same numbers as the lines required for the subsequent stage of the low-pass filter 123, the high-pass filter 127, the low-pass filter 143, and the high-pass filter 147, respectively. The specific number of lines required for the vertical filter is a half of "the number of taps plus one" if the vertical filter has an odd number of taps, while the number of lines equal to a half of the number of taps is needed if the vertical filter has an even number of taps. If the low-pass filter, such as the one shown in FIG. 35A, is used, two line memory units are disposed in the subsequent level of the low-pass filter 123. The numbers of line memory units required for the memory devices 121, 125, 141, 145, 150, 154, 160 and 164 illustrated in FIG. 34 are different from the numbers of memory devices 73, 79, 86 and 103 provided for the wavelet transformer 51 shown in FIG. 32 because up-sampling processing in the vertical direction is executed in a stage between the memory devices and the filters of the inverse-wavelet transformer 52, which operation will be explained in detail below.
Vertical up-sampling units 122, 126, 142 and 146 insert one line containing no data between the adjacent input lines according to the following equation (13).
[Mathematical equation 3] ##EQU3##
The respective frequency-band signals LLLL[i",j"], LHLL[i",j"], HLLL[i",j"], and HHLL[i",j"], which have been up-sampled in the up-sampling units 122, 126, 142 and 146, are interpolated in the vertical direction by the low-pass filter 123, the high-pass filter 127, the low-pass filter 143, and the high-pass filter 147. The interpolated signals output from the low-pass filter 123 and the high-pass filter 127 are transmitted to an adder 124, while the interpolated signals output form the low-pass filter 143 and the high-pass filter 147 are sent to an adder 144. The synthesizing filters 123, 127, 143 and 147, as well as the corresponding analyzing filters 80, 82, 87 and 89, should be configured to satisfy the foregoing equations (9) and (10). If the coefficients shown in FIG. 33 are used for the analyzing filters, the filters having the coefficients illustrated in FIG. 35 should be used as the synthesizing filters.
The interpolated frequency-band signals LLLL[i",j"] and LHLL[i",j"] are added in the adder 124 and output to a horizontal up-sampling unit 128. Meanwhile, the interpolated signals HLLL[i",j"] and HHLL[i",j"] are added in the adder 144 and output to a horizontal up-sampling unit 148. The up-sampling units 128 and 148 perform the up-sampling operation on the respective signals in the horizontal direction according to the following equation (14).
[Mathematical equation 4] ##EQU4##
Thereafter, the horizontal low-pass filter 129 and the high-pass filter 149 conduct filtering operations in the horizontal direction on the respective signals which have been sampled by the up-sampling units 128 and 148, respectively. The filtered signals are then interpolated in the filters 129 and 149, and the interpolated signals are further added in an adder 140. The low-frequency-band signal LL[i',j'] is thus reproduced.
Subsequently, the components from the memory device 150 to the adder 159 execute processing on the reproduced signal LL[i',j'], and the input frequency-band signals LH[i',j'], HL[i',j'], and HH[i',j'] in a manner similar to the operation performed by the components from the above-described memory device 121 to the adder 140. As a consequence, an image signal I[i,j] is thus reproduced.
As illustrated in FIG. 25, a known de-quantizer performs a de-quantizing operation with a quantizing step of the same size as the quantizing step used in the quantizer. Accordingly, the reproduced value is generally positioned at the center of each of the ranges incremented by the quantizing steps (de-quantizing steps). In the above type of "linear quantization", quantizing errors can be minimized when the input data is, as shown in FIG. 36, uniformly distributed in each of the ranges incremented by the quantizing steps.
In contrast, in motion-picture encoding the DCT coefficients and the wavelet coefficients used for a motion-compensated differential image have a distribution, as illustrated in FIG. 26, in which the frequency sharply drops with the increased absolute value, and its local distribution is also nonuniform, as shown in FIG. 37. Particularly when data is encoded with a low bit rate, a large size Q of quantizing step is used. Accordingly, the absolute values of the most coefficients range from 0 to Q. As a consequence, a greater number of quantizing errors occur in the nonuniform data in the conventional linear quantizer and de-quantizer.
To overcome the above drawback, "nonlinear quantization" and "nonlinear de-quantization" in which a smaller quantizing step is used for a larger level of distribution frequency are performed on the data having a large distribution. This method on one hand decreases quantizing errors, but on the other hand increases the generated amount of bits. Moreover, nonlinear quantizing and de-quantizing processing is very complicated.
Further, the motion-picture encoding/decoding apparatus shown in FIGS. 28 and 29 which utilizes both DCT and motion compensation is employed for the international standard methods, such as MPEG1, MPEG2, and H.263, and is most widely being used. However, since processing is executed by a block unit, a great amount of block noise is generated particularly with a low bit rate.
Conversely, the generation of block noise can be suppressed because processing is executed by a frame unit in the known motion-picture encoding and decoding apparatus utilizing wavelet transform shown in FIGS. 30 and 31. Ringing noise, however, which is unique to wavelet encoding in a flat (non-edge) region, is produced, and the ringing phase further changes in every frame when a motion picture is reproduced, thereby generating temporal jitter of motion pictures.
Moreover, the wavelet encoding method encounters the following problem. If one quantized coefficient is. much larger than the other coefficients among the coefficients of different frequency bands in the same spatial position, the pattern of a wavelet filter disadvantageously emerges on a decoded image. Flickering of the filter pattern also appears if a coefficient much larger than the other coefficients unstably appears temporally. As a consequence, the quality of a displayed image is degraded.